package com.test.daily.leetcode.y2022.m05.day0526.v02;

import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/5/26 下午 04:41
 * @version: 1.0
 */
public class Solution {
    public static class Node<V> {
        V value;

        public Node(V value) {
            this.value = value;
        }
    }

    public static class UnionFind<V> {
        HashMap<V, Node<V>> nodes;
        HashMap<Node<V>, Node> parentMap;
        HashMap<Node<V>, Integer> sizeMap;

        public UnionFind(List<V> list) {
            for (V v : list) {
                Node<V> cur = new Node(v);
                nodes.put(v, cur);
                sizeMap.put(cur, 1);
                parentMap.put(cur, cur);
            }
        }

        public Node<V> findFather(Node<V> cur) {
            Stack<Node<V>> stack = new Stack<>();
            while (cur != parentMap.get(cur)) {
                stack.push(cur);
                cur = parentMap.get(cur);
            }
            while (!stack.isEmpty()) {
                parentMap.put(stack.pop(), cur);
            }
            return cur;
        }

        public void union(Node<V> a, Node<V> b) {
            Node<V> aHead = findFather(a);
            Node<V> bHead = findFather(b);
            if (aHead != bHead) {
                Node<V> small = sizeMap.get(a) < sizeMap.get(b) ? aHead : bHead;
                Node<V> big = small == aHead ? bHead : aHead;
                sizeMap.put(big, sizeMap.get(small) + sizeMap.get(big));
                sizeMap.remove(small);
                parentMap.put(small, big);
            }
        }

        public int sets() {
            return sizeMap.size();
        }
    }
}
